package org.wyw.solution;

@Solution(
        id = 5,
        title = "合并两个有序数组",
        difficulty = "medium",
        link = "https://leetcode.cn/problems/merge-sorted-array/description/"
)
public class Solution005 {
    /**
     * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
     *
     * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
     * 最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n
     *
     * 思路：用两个指针分别从后往前遍历两个数组，最大的放在最后面。。。
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m -1 , j = n - 1 , k = m + n - 1;
        while (i>=0 && j>=0){
            if (nums1[i] >nums2[j]){
                nums1[k--] = nums1[i--];
            }else {
                nums1[k--] = nums2[j--];
            }
        }
        //此时，可能还有一个数组还有元素，若是nums1，则不用管，若剩下的是nums2的元素，直接赋值即可，因为数组是有序数组
        while (j>=0){
            nums1[k--] = nums2[j--];
        }
    }



}
